/*
 * @lc app=leetcode.cn id=30 lang=cpp
 *
 * [30] 串联所有单词的子串
 */
#include "include.h"
// @lc code=start
class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        int wordLength = words[0].size();
        int wordNum = words.size();

        std::unordered_map<std::string, int> wordsHash;
        for (auto& word : words){
            wordsHash[word] += 1;
        }

        std::unordered_map<std::string, std::vector<int>> wordsPosition;
        for (auto& wordInfo : wordsHash){
            auto iter = wordsPosition.emplace(wordInfo.first, std::vector<int>());
            findSubString(s, wordInfo.first, iter.first->second, wordNum*wordLength);
        }

        // printf("-------------------------\n");
        // for (auto& wordPos : wordsPosition){
        //     printf("%s pos : ", wordPos.first.c_str());
        //     for (int pos : wordPos.second){
        //         printf("%d ", pos);

        //         // auto nextWord = s.substr(pos+wordLength, wordLength);
        //         // printf("%s ", nextWord.c_str());
        //     }
        //     printf("\n");
        // }
        // printf("-------------------------\n");

        vector<int> res;

        for (auto& wordPos : wordsPosition){
            for (int pos : wordPos.second){
                ;
                int localPos = pos;
                bool succeed = true;
                int currentWordNum = 1;
                auto localWordsHash = wordsHash;
                localWordsHash[wordPos.first] -= 1;
                while (currentWordNum < wordNum){
                    auto nextWord = s.substr(localPos + wordLength, wordLength);
                    auto iter = localWordsHash.find(nextWord);
                    if (iter == localWordsHash.end()){
                        succeed = false;
                        break;
                    }else{
                        if (iter->second == 0){
                            succeed = false;
                            break;
                        }else{
                            currentWordNum += 1;
                            localPos += wordLength;
                            iter->second -= 1;
                        }
                    }
                }
                if (succeed){
                    res.emplace_back(pos);
                }
                ;
            }
        }

        return res;
    }
private:
    void findSubString(const string& s, const string& word, std::vector<int>& res, int minLength){
        int startPos = 0;
        int pos = s.find(word, 0);
        while (pos != -1){
            // startPos = pos + word.size();
            startPos = pos + 1;

            int leftCharNum = s.size() - pos;
            if (leftCharNum < minLength){break;}

            res.emplace_back(pos);
            pos = s.find(word, startPos);
        }
    }

    // inline bool isSubString(const string& s, const string& word)
};
// @lc code=end

// "wordgoodgoodgoodbestword"\n["word","good","best","word"]
// "barfoofoobarthefoobarman"\n["bar","foo","the"]

int main(){
    string s = "barfoothefoobarman";
    vector<string> words = {"foo","bar"};
    Solution test;
    test.findSubstring(s, words);
}

// "aaaaaaaaaaaaaa"\n["aa","aa"]
